﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Diagnostics;

namespace SimpleIR
{
	public sealed class IRProgram
	{
		internal static CtrGen GlobalRefCtrGen;
		private readonly Dictionary<IRMemberField[], IRBasicAccessPath> m_accpintern;
		private readonly Dictionary<IRMemberField, IRBasicAccessPath> m_singletonaccp;
		private readonly List<IRBasicAccessPath> m_orderaccplist;
		
		private readonly IRTypeTable m_typeTable;
		private readonly IRIdentifierTable m_nameTable;
		private readonly IRInvocationTable m_invokeTable;

		private readonly CallGraph m_callGraph;

		private readonly BodyDefTable m_bodyTable;

		public static void InitializeRefCounter()
		{ GlobalRefCtrGen = new CtrGen(); }

		/// <summary>
		/// Initialize all the data structures to their base values ready for a frontend to load in program information.
		/// </summary>
		public IRProgram()
		{
			this.m_accpintern = new Dictionary<IRMemberField[], IRBasicAccessPath>(new IRBasicAccessPathComparer());
			this.m_accpintern.Add(IRBasicAccessPath.EmptyAccessPath.Path, IRBasicAccessPath.EmptyAccessPath);

			this.m_singletonaccp = new Dictionary<IRMemberField, IRBasicAccessPath>();
			this.m_orderaccplist = new List<IRBasicAccessPath>();

			this.m_typeTable = new IRTypeTable();
			this.m_nameTable = new IRIdentifierTable();
			this.m_invokeTable = new IRInvocationTable();

			this.m_callGraph = new CallGraph();

			this.m_bodyTable = new BodyDefTable();
		}

		public void ReportOnProgramMetrics()
		{
			int mcount = 0;
			HashSet<IRType> tset = new HashSet<IRType>();
			int maxbc = 0;

			foreach(IRBodyDef b in this.m_bodyTable.BodyList)
			{
				mcount++;
				tset.Add(b.InvokeID.DefInClass);

				if(b.IsAbstract || b.IsBuiltin)
					continue;

				maxbc = Math.Max(maxbc, b.Body.T1T2Body.MaxStmt());
			}

			Console.WriteLine("IR Data:");
			Console.WriteLine("  Type Count:     " + tset.Count);
			Console.WriteLine("  Method Count:   " + mcount);
			Console.WriteLine("  Bytecode Count: " + maxbc);
		}

		public override String ToString()
		{
			StringBuilder sb = new StringBuilder();
			foreach(IRBodyDef b in this.m_bodyTable.BodyList)
			{
				if(b.IsAbstract || b.IsBuiltin)
					continue;

				sb.Append("+++++++++++++++++\n");
				sb.Append(b.ToString());
			}
			return sb.ToString();
		}

		/// <summary>
		/// Compute all the type relations in this, subtypes, visible/reachable fields, recursive type info.
		/// </summary>
		public void LoadTypeInfo()
		{
			this.m_typeTable.ComputeAllBoxedTypeInfo(this.m_nameTable);
			this.m_typeTable.CompleteRefAndPointerTypeInfo();
			this.m_typeTable.ComputeAllChildClasses();
			this.m_typeTable.ComputeAllVisFieldInfo();

			//set the access path info
			List<IRType> alltypes = this.m_typeTable.AllDefinedTypes;
			foreach(IRType tt in alltypes)
			{
				List<IRBasicAccessPath> bapl = new List<IRBasicAccessPath>();
				this.GetAllAccessPathsForType(tt, bapl);
				tt.TypeDescription.AllTerminalAccessPaths.AddRange(bapl);
			}

			//order all access paths
			this.m_orderaccplist.AddRange(this.m_accpintern.Values);
			IRBasicAccessPath.SetAccessPathCompareInfo(this.m_orderaccplist);

			//order the access paths in the type definitions too
			foreach(IRType tt in alltypes)
				tt.TypeDescription.AllTerminalAccessPaths.Sort();

			//order all invoke identifiers
			this.m_invokeTable.ComputeInvokeIDStableOrder();

			this.m_typeTable.ComputeRecursiveTypeInfo();
		}

		/// <summary>
		/// Do some simple processing to clean up the IR, link in the static constructors
		/// Start by linking any any needed calls (static constructors etc.) then build the call graph and compute the field use/mod + purity closures, 
		/// propagate this info through the IR, then simplify the basic instructions
		/// </summary>
		public void PreProcLinkAndSimplify()
		{
			////////////////////////////
			//get the main method and right after the first stmt add calls to each static constructor
			IRBodyDef maindb = this.m_bodyTable.BodyList.Find((IRBodyDef bd) => (bd.InvokeID.InvSig is IRStaticInvoke) && bd.InvokeID.InvSig.InvokeName.Equals("Main"));
			List<IRStaticInvoke> staticInits = this.m_invokeTable.GetAllNeededStaticConstructors();
			IRType voidtype = this.TypeTable.LookupTypeForName("System.Void");
			maindb.Body.AddStaticConstructorCalls(staticInits, voidtype);

			//////////////////////////
			//Do call graph and fully resolved component construction
			Dictionary<IRLambdaType, HashSet<IRInvokeIdentity>> delegateinvmap = new Dictionary<IRLambdaType, HashSet<IRInvokeIdentity>>();

			foreach(IRBodyDef bdf in this.MethodBodyTable.BodyList)
				this.CallGraph.AddCallNode(bdf.InvokeID);

			foreach(IRBodyDef bdf in this.MethodBodyTable.BodyList)
			{
				if((!bdf.IsBuiltin) & (!bdf.IsAbstract))
					bdf.Body.InitUsedStaticsDelegateTargetInfo(bdf.UsedModStaticFields, delegateinvmap);
			}

			foreach(IRBodyDef bdf in this.MethodBodyTable.BodyList)
				bdf.ComputeCallGraph(this.CallGraph, delegateinvmap, this);

			this.CallGraph.ComputeRecCallInfo(this);
		}

		/// <summary>
		/// Build T1-T2 forms of methods.
		/// </summary>
		public void BuildT1T2()
		{
			CtrGen stmtcg = new CtrGen();
			foreach(IRBodyDef bdf in this.m_bodyTable.BodyList)
			{
				if((!bdf.IsBuiltin) & (!bdf.IsAbstract))
				{
					bdf.Body.BuildT1T2();
					bdf.Body.NumberBody(stmtcg);

					HashSet<IRVarName> mparams = new HashSet<IRVarName>(bdf.Parameters);
					if(bdf.InvokeID.InvSig is IRVirtualInvoke)
						mparams.Add(this.m_nameTable.LookupLocalVarName("this"));
				}
			}
		}

		/// <summary>
		/// Return true if the given type is already interned.
		/// </summary>
		public bool IsTypeNamedInterned(String tn)
		{ return this.m_typeTable.IsTypeNameInterned(tn); }

		/// <summary>
		/// Get the type for the given interned type name.
		/// </summary>
		public IRType LookupTypeForName(String tn)
		{ return this.m_typeTable.LookupTypeForName(tn); }

		/// <summary>
		/// Intern a given type, use the above method to determine the type id that the type should have.
		/// </summary>
		public void InternTypeName(IRType tt)
		{ this.m_typeTable.InternNewType(tt); }

		/// <summary>
		/// Intern a member field definition.
		/// </summary>
		public IRMemberField FullyInternMemberField(IRType defClass, string name, IRType fieldType, FieldQualifiers fq)
		{
			IRMemberField mfd = defClass.TypeDescription.LoadFieldInfoAsNeeded(defClass, name, fieldType, fq);

			if(!this.m_singletonaccp.ContainsKey(mfd))
			{
				IRBasicAccessPath bap = new IRBasicAccessPath(new IRMemberField[] { mfd });
				this.m_singletonaccp.Add(mfd, bap);
				this.m_accpintern.Add(new IRMemberField[] { mfd }, bap);
			}

			return mfd;
		}

		/// <summary>
		/// Intern a static field definition.
		/// </summary>
		public IRStaticField InternNewStaticFieldFull(IRType defClass, string name, IRType fieldType, FieldQualifiers fq)
		{ return this.m_nameTable.InternNewStaticField(fq, defClass, name, fieldType); }

		/// <summary>
		/// Intern a local variable name.
		/// </summary>
		public IRVarName InternNewLocalVar(string name)
		{ return this.m_nameTable.InternNewLocalVar(name); }

		/// <summary>
		/// Return the access path with the given identifier.
		/// </summary>
		public IRBasicAccessPath GetAccessPathWithID(int accpid)
		{ return this.m_orderaccplist[accpid]; }

		/// <summary>
		/// We keep all of out access paths intered in a nice table so this to get the singleton basic access path for the given member field.
		/// </summary>
		public IRBasicAccessPath GetAccessPathForSingleField(IRMemberField f)
		{
			if(!this.m_singletonaccp.ContainsKey(f))
			{
				IRMemberField[] amfa = new IRMemberField[] { f };
				IRBasicAccessPath accp = new IRBasicAccessPath(amfa);
				this.m_singletonaccp.Add(f, accp);
				this.m_accpintern.Add(amfa, accp);
			}

			return this.m_singletonaccp[f];
		}

		/// <summary>
		/// We keep all of out access paths intered in a nice table so this to get the tail of the current path.
		/// </summary>
		public IRBasicAccessPath GetAccessPathTail(IRBasicAccessPath accp)
		{
			if(accp.Tail != null)
				return accp.Tail;
			else
			{
				IRMemberField[] mfa = new IRMemberField[accp.Path.Length - 1];
				Array.Copy(accp.Path, 1, mfa, 0, mfa.Length);
				if(this.m_accpintern.ContainsKey(mfa))
					accp.Tail = this.m_accpintern[mfa];
				else
				{
					IRBasicAccessPath bap;
					if(mfa.Length == 1)
						bap = this.GetAccessPathForSingleField(mfa[0]);
					else
					{
						bap = new IRBasicAccessPath(mfa);
						this.m_accpintern.Add(mfa, bap);
					}
					
					accp.Tail = bap;
				}

				return accp.Tail;
			}
		}

		/// <summary>
		/// Get Kth tail of a given path.
		/// e.g. given <c>currentpath</c> is [f1, ..., fk, fk+1, ..., fj] return [fk+1, ..., fj]
		/// </summary>
		public IRBasicAccessPath GetAccessPathTailK(IRBasicAccessPath accp, int k)
		{
			IRBasicAccessPath bap = accp;
			while(k > 0)
			{
				bap = this.GetAccessPathTail(bap);
				--k;
			}

			return bap;
		}

		/// <summary>
		/// We keep all of out access paths intered in a nice table so this to get the postfix extension of a given path.
		/// e.g. given <c>currentpath</c> is [f1, ..., fk] and <c>ext</c> is fj return [f1, ..., fk, fj]
		/// </summary>
		public IRBasicAccessPath GetAccessPathExtensionPost(IRBasicAccessPath currentpath, IRMemberField ext)
		{
			Dictionary<IRMemberField, IRBasicAccessPath> extpmap = currentpath.PostExtensionMap;
			if(extpmap.ContainsKey(ext))
				return extpmap[ext];
			else
			{
				IRMemberField[] extp = new IRMemberField[currentpath.Path.Length + 1];
				Array.Copy(currentpath.Path, 0, extp, 0, currentpath.Path.Length);
				extp[currentpath.Path.Length] = ext;

				IRBasicAccessPath bap;
				if(this.m_accpintern.ContainsKey(extp))
					bap = this.m_accpintern[extp];
				else
				{
					if(extp.Length == 1)
						bap = this.GetAccessPathForSingleField(extp[0]);
					else
					{
						bap = new IRBasicAccessPath(extp);
						this.m_accpintern.Add(extp, bap);
					}
				}

				extpmap.Add(ext, bap);
				return bap;
			}
		}

		/// <summary>
		/// We keep all of out access paths intered in a nice table so this to get the postfix extension of a given path.
		/// e.g. given <c>currentpath</c> is [f1, ..., fk] and <c>ext</c> is [fj, ..., fl] return [f1, ..., fk, fj, ..., fl]
		/// </summary>
		public IRBasicAccessPath GetAccessPathExtensionPost_WPath(IRBasicAccessPath currentpath, IRBasicAccessPath extpath)
		{
			if(extpath == null)
				return currentpath;
			else
			{
				IRBasicAccessPath bap = currentpath;
				for(int i = 0; i < extpath.Path.Length; ++i)
					bap = this.GetAccessPathExtensionPost(bap, extpath.Path[i]);

				return bap;
			}
		}

		/// <summary>
		/// Get all the access paths that can be used within the given type definition.
		/// </summary>
		public void GetAllAccessPathsForType(IRType tt, List<IRBasicAccessPath> allp)
		{
			foreach(IRMemberField mf in tt.TypeDescription.AllVisibleFields)
			{
				IRBasicAccessPath iip = this.GetAccessPathForSingleField(mf);
				this.GetAllAccessPathsForTypeAndExtensionsOf(mf.FieldType, iip, allp);
			}
		}

		/// <summary>
		/// Given a initial access path find all extensions of it within the type tt.
		/// </summary>
		public void GetAllAccessPathsForTypeAndExtensionsOf(IRType tt, IRBasicAccessPath initpath, List<IRBasicAccessPath> allp)
		{
			if((tt is IRStructType) || (tt is IRClassType))
			{
				foreach(IRMemberField mf in tt.TypeDescription.AllVisibleFields)
				{
					IRBasicAccessPath iip = this.GetAccessPathExtensionPost(initpath, mf);
					this.GetAllAccessPathsForTypeAndExtensionsOf(mf.FieldType, iip, allp);
				}
			}
			else
			{
				allp.Add(initpath);
			}
		}

		/////////////////////////////////////////////////////////////
		//Type Conversion

		/// <summary>
		/// If we are loading a value onto the stack convert it to the standard long, ulong or, double value for primitives and leave the 
		/// type unchanged otherwise.
		/// </summary>
		public IRType ConvertTypeToStdStackRep(IRType tt)
		{
			IRType tt2 = (tt is IREnumType) ? ((IREnumType)tt).UnerlyingNumericType : tt;

			if(tt2 is IRPrimitiveType)
			{
				if(tt2 is IRSignedIntegerType)
				{
					if(((IRSignedIntegerType)tt2).SignedTag == IRSignedIntegerType.SignedTypeTag.Int64Tag)
						return this.TypeTable.EvalStackInt64Type;
					else
						return this.TypeTable.EvalStackInt32Type;
				}
				else if(tt2 is IRUnSignedIntegerType)
				{
					if(((IRUnSignedIntegerType)tt2).UnSignedTag == IRUnSignedIntegerType.UnsignedTypeTag.UInt64Tag)
						return this.TypeTable.EvalStackInt64Type;
					else
						return this.TypeTable.EvalStackInt32Type;
				}
				else if(tt2 is IRFloatingPointType)
				{
					return this.TypeTable.EvalStackFloatType;
				}
				else
				{
					return tt2;
				}
			}
			else
			{
				return tt2;
			}
		}

		/// <summary>
		/// True if type t1 can be assigned to type t2 (i.e. <c>t2 := t1</c> is ok in the relaxed type system).
		/// </summary>
		public bool IsT1AssignableToT2(IRType t1, IRType t2)
		{
			if(t1 == t2)
				return true;
			
			if((t1 is IRPrimitiveType) & (t2 is IRPrimitiveType))
				return IRPrimitiveType.IsT1AssignableToT2((IRPrimitiveType)t1, (IRPrimitiveType)t2);
			else if((t1 is IRValueType) & (t2 is IRValueType))
				return (t1 == t2 ? true : false);
			else if((t1 is IRReferenceType) & (t2 is IRReferenceType))
			{
				IRType tt1 = ((IRReferenceType)t1).ReferenceTargetType;
				IRType tt2 = ((IRReferenceType)t2).ReferenceTargetType;
				return (tt1 == tt2 ? true : false);
			}
			else if((t1 is IRPtrType) & (t2 is IRPtrType))
			{
				if(((IRPtrType)t1).IsNullPointer)
					return true;
				else if(((IRPtrType)t2).IsNullPointer)
					return false;
				else
				{
					IRClassType tt1 = ((IRPtrType)t1).PtrTargetType;
					IRClassType tt2 = ((IRPtrType)t2).PtrTargetType;

					return this.IsT1SubTypeOfT2(tt1, tt2);
				}
			}
			else
				return true;
		}

		private bool IsT1SubTypeOfT2(IRClassType t1, IRClassType t2)
		{
			if(t1 == t2)
				return true;
			else if(t1 == this.m_typeTable.RootObjectType)
				return false;
			else
				return t2.TypeDescription.AllSubTypes.Contains(t1);
		}

		/// <summary>
		/// Return true there are any recursive types in the two lists.
		/// </summary>
		public static bool AnyTypesInSetsRecursive(List<IRType> ttl1, List<IRType> ttl2)
		{
			for(int i = 0; i < ttl1.Count; ++i)
			{
				IRType tt1 = ttl1[i];
				if(tt1.TypeDescription.AllRecursiveWith.Overlaps(ttl2))
					return true;
			}

			return false;
		}

		/////////////////////////////////////////////////////////////
		//Method invocation resolution routines

		/// <summary>
		/// Lookup all the invocation targets for a given virtual call.
		/// </summary>
		public HashSet<IRInvokeIdentity> GetPossibleInvocationTargetsForVirtCallExp(IRType recivertype, Tuple<IRType, IRInvokeSig> nettypeandvsig)
		{
			HashSet<IRInvokeIdentity> iid = new HashSet<IRInvokeIdentity>();

			IRType declaredCallVType = null;
			if(recivertype is IRStructType)
				declaredCallVType = recivertype;
			else if(recivertype is IRReferenceType)
				declaredCallVType = ((IRReferenceType)recivertype).ReferenceTargetType;
			else
			{
				IRPtrType ppty = (IRPtrType)recivertype;
				if(ppty.PtrTargetType is IRBoxedType)
					declaredCallVType = ((IRBoxedType)ppty.PtrTargetType).BoxedTypeValue;
				else
					declaredCallVType = ppty.PtrTargetType;
			}

			Debug.Assert(!(declaredCallVType is IRReferenceType), "Huh, how are we invoking this method");

			foreach(IRType concsubt in declaredCallVType.TypeDescription.AllSubTypes)
			{
				//we can never create an object of an abstract type so we will never invoke a method on it (and boxed types always get transformed to the unboxed versions)
				//note we should explicitly set all value types as inheriting from object so this finds the appropriate functions.
				if((!concsubt.TypeDescription.IsAbstractType) && (!(concsubt is IRBoxedType)))
				{
					IRType callimplin = IRProgram.GetImplClassWithThisAsBaseType(concsubt, nettypeandvsig);
					IRInvokeIdentity invid = this.GetInvocationSigInGivenType(callimplin, nettypeandvsig);
					Debug.Assert(invid != null, "Something is not ok.");

					iid.Add(invid);
				}
			}

			return iid;
		}

		/// <summary>
		/// Given a method sig get the corresponding InvokeIdentity from this class.
		/// </summary>
		private IRInvokeIdentity GetInvocationSigInGivenType(IRType basetype, Tuple<IRType, IRInvokeSig> nettypeandvsig)
		{
			IRInvokeSig match;
			if(basetype.TypeDescription.AllExplicitOverridesMap.ContainsKey(nettypeandvsig))
				match = basetype.TypeDescription.AllExplicitOverridesMap[nettypeandvsig];
			else
				match = nettypeandvsig.Item2;

			return this.InvokeTable.LookupInvokeIdentity(basetype, match);
		}

		/// <summary>
		/// For use when looking up call targets in a class, this finds the sig as needed.
		/// </summary>
		public IRBodyDef GetBodyForClassAndSig(IRType cd, Tuple<IRType, IRInvokeSig> nettypeandvsig)
		{
			IRInvokeSig sig;
			if(cd.TypeDescription.AllExplicitOverridesMap.ContainsKey(nettypeandvsig))
				sig = cd.TypeDescription.AllExplicitOverridesMap[nettypeandvsig];
			else
				sig = nettypeandvsig.Item2;

			List<IRBodyDef> bdff = this.m_bodyTable.BodyListForClass(cd);
			IRBodyDef bd = bdff.Find((IRBodyDef bdd) => bdd.InvokeID.InvSig == sig);
			return bd;
		}

		/// <summary>
		/// Given a method sig resolve the class that implments this call starting from this class as the reciver argument (return null if no implementation found).
		/// </summary>
		public static IRType GetImplClassWithThisAsBaseType(IRType basetype, Tuple<IRType, IRInvokeSig> nettypeandvsig)
		{
			if(basetype.TypeDescription.AllExplicitOverridesMap.ContainsKey(nettypeandvsig))
				return basetype;
			else
			{
				IRInvokeSig tvsig = nettypeandvsig.Item2;

				if(basetype.TypeDescription.AllImplMemberMethods.Contains(tvsig))
					return basetype;
				else
				{
					foreach(IRType iht in basetype.TypeDescription.AllInheritsExtends)
					{
						IRType rtt = GetImplClassWithThisAsBaseType(iht, nettypeandvsig);
						if(rtt != null)
							return rtt;
					}

					return null;
				}
			}
		}

		////////
		//General accessors.

		public IRTypeTable TypeTable
		{ get { return this.m_typeTable; } }

		public IRIdentifierTable NameTable
		{ get { return this.m_nameTable; } }

		public IRInvocationTable InvokeTable
		{ get { return this.m_invokeTable; } }

		public CallGraph CallGraph
		{ get { return this.m_callGraph; } }

		public BodyDefTable MethodBodyTable
		{ get { return this.m_bodyTable; } }
	}
}
